home *** CD-ROM | disk | FTP | other *** search
/ PD ROM 1 / PD ROM Volume I - Macintosh Software from BMUG (1988).iso / Programming / Complete Applications / Othello C Source / move.c < prev    next >
Encoding:
C/C++ Source or Header  |  1985-06-16  |  7.5 KB  |  278 lines  |  [TEXT/ttxt]
  1. /* move.c - ChooseMove, EvalMove, analyze, RestoreBoard, SortMoves */
  2.  
  3. #include "mac/quickdraw.h"
  4. #include "mac/osintf.h"
  5. #include "mac/toolintf.h"
  6. #include "othello.h"
  7.  
  8. unsigned short Random();
  9. short EvalMove(), analyze();
  10.  
  11. short position[BOARDSIZE+2][BOARDSIZE+2] =
  12.     {  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
  13.        0, 20,  3,  4,  4,  4,  4,  3, 20,  0,
  14.        0,  3, -7, -1, -1, -1, -1, -7,  3,  0,
  15.        0,  4, -1,  0,  0,  0,  0, -1,  4,  0,
  16.        0,  4, -1,  0,  0,  0,  0, -1,  4,  0,
  17.        0,  4, -1,  0,  0,  0,  0, -1,  4,  0,
  18.        0,  4, -1,  0,  0,  0,  0, -1,  4,  0,
  19.        0,  3, -7, -1, -1, -1, -1, -7,  3,  0,
  20.        0, 20,  3,  4,  4,  4,  4,  3, 20,  0,
  21.        0,  0,  0,  0,  0,  0,  0,  0,  0,  0 };
  22.  
  23. BoardArray    WorkBoard;
  24. int    OrigLookAhead;
  25. int    skill = 0;
  26. int    StopThinking = FALSE;
  27. int    nTicks[nTimed] = {0, 0, 0, 0, 0};
  28.  
  29.  
  30.  
  31. ChooseMove(move, board)
  32. MoveRecord    *move;
  33. BoardArray    board;
  34. {
  35.     MoveList    moves;
  36.     int        nMoves, i;
  37.     int        ticks, other;
  38.     short        analysis;
  39.     register int    row, col;
  40.     
  41.     for (i = 0; i < nTimed; ++i)
  42.         nTicks[i] = 0;
  43.     ticks = TickCount();
  44.     StopThinking = FALSE;
  45.     analysis = 0;
  46.     for (row = 1; row <= BOARDSIZE; ++row)
  47.         for (col = 1; col <= BOARDSIZE; ++col) {
  48.         board[row][col] &= stoneColor;
  49.         WorkBoard[row][col] = board[row][col];
  50.         if ((board[row][col] & stoneColor) == curColor)
  51.             analysis += position[row][col];
  52.         else if ((board[row][col] & stoneColor) == opposite(curColor))
  53.             analysis -= position[row][col];
  54.         }
  55. #ifdef UNDEF
  56.     nMoves = FindMoves(opposite(curColor), WorkBoard, moves, ALL);
  57.     for (i = 0; i < nMoves; ++i)
  58.         moves[i].value = EvalMove(moves[i], WorkBoard,
  59.             opposite(curColor), skill - 1);
  60.     SortMoves(moves, nMoves);
  61.     for (i = 0; moves[i].value == moves[0].value; ++i)
  62.         WorkBoard[moves[i].row][moves[i].col] |= threat;
  63. #endif
  64.     nMoves = FindMoves(curColor, WorkBoard, moves, ALL);
  65.     if (nStones[stoneEmpty] > EndGame)
  66.         OrigLookAhead = skill;
  67.     else
  68.         OrigLookAhead = EndGame;
  69.     for (i = 0; i < nMoves; ++i)
  70.         moves[i].value = EvalMove(moves[i], WorkBoard, curColor,
  71.                     OrigLookAhead);
  72.     SortMoves(moves, nMoves);
  73.     while (moves[--nMoves].value < moves[0].value)
  74.         ;
  75.     ++nMoves;
  76.     *move = moves[Random() % nMoves];
  77.     analysis += move->value;
  78.     ticks = TickCount() - ticks;
  79.     if (!trace || StopThinking)
  80.         ClearMessages();
  81.     else {
  82.         sprintf(note1, "Analysis = %d (%d)", analysis, move->value);
  83.         sprintf(note2, "fm %d%% df %d%% a %d%% r %d%%",
  84.             100 * nTicks[pFindMoves]    / ticks,
  85.             100 * nTicks[pDoFlips]        / ticks,
  86.             100 * nTicks[pAnalyze]        / ticks,
  87.             100 * nTicks[pRestoreBoard]    / ticks);
  88.         other = ticks;
  89.         for (i = 0; i < nTimed; ++i)
  90.             other -= nTicks[i];
  91.         sprintf(note3, "sort %d%% other %d%%",
  92.             100 * nTicks[pSortMoves]    / ticks,
  93.             100 * other            / ticks);
  94.     }
  95. }
  96.  
  97. short EvalMove(move, board, color, LookAhead)
  98. MoveRecord    move;
  99. BoardArray    board;
  100. int        color, LookAhead;
  101. {
  102.     register int    row, col, i;
  103.     MoveList    flips, moves, oflips;
  104.     int        nFlips, nMoves, nToTry, nOFlips;
  105.     short        value, best, factor, analysis;
  106.     int        OrigTrace;
  107.  
  108.     DoEvent();            /* Respond to the user.        */
  109.     OrigTrace = trace;
  110.     analysis = analyze(move, color, flips, &nFlips, board, OrigTrace);
  111.     if (LookAhead <= 0 || LookAhead <= OrigLookAhead - MaxLookAhead ||
  112.         nStones[stoneEmpty] <= 0 || StopThinking) {
  113.         RestoreBoard(board, move, flips, nFlips, OrigTrace);
  114.         return(analysis);
  115.     }
  116.     best = minValue;
  117.     if ((nMoves=FindMoves(opposite(color), board, moves, RESTRICT)) > 0 ||
  118.         (nMoves=FindMoves(opposite(color), board, moves, ALL)) > 0) {
  119.         /* Subtract opponent's best choice */
  120.         color = opposite(color);
  121.         factor = -1;
  122.     }
  123.     else if ((nMoves = FindMoves(color, board, moves, ALL)) > 0)
  124.         /* Opponent can't move; evaluate my further choices */
  125.         factor = 1;
  126.     else {
  127.         /* Game is over (no one can move); count up stones */
  128.         value = 0;
  129.         for (row = 1; row <= BOARDSIZE; ++row)
  130.             for (col = 1; col <= BOARDSIZE; ++col)
  131.             switch (board[row][col] & stoneColor) {
  132.             case stoneWhite:
  133.                 ++value;
  134.                 break;
  135.             case stoneBlack:
  136.                 --value;
  137.                 break;
  138.             }
  139.         if (color == stoneBlack)
  140.             value = -value;
  141.         RestoreBoard(board, move, flips, nFlips, OrigTrace);
  142.         return(100 * value);
  143.     }
  144.     for (i = 0; i < nMoves; ++i) {
  145.         moves[i].value = analyze(moves[i], color, oflips, &nOFlips,
  146.             board, OrigTrace);
  147.         RestoreBoard(board, moves[i], oflips, nOFlips, OrigTrace);
  148.     }
  149.     SortMoves(moves, nMoves);
  150.     if (LookAhead < skill)
  151.         nToTry = nMoves * LookAhead*LookAhead/(skill*skill) + 1;
  152.     else
  153.         nToTry = nMoves;
  154.     for (i = 0; i < nToTry; ++i) {
  155.         if (moves[i].value < 0 && moves[i].value < moves[0].value)
  156.             break;
  157.         if ((value = EvalMove(moves[i], board, color, LookAhead-1)) <
  158.             best - 10)
  159.             break;
  160.         if (value > best)
  161.             best = value;
  162.     }
  163.     RestoreBoard(board, move, flips, nFlips, OrigTrace);
  164.     if (skill <= 1)
  165.         return(analysis + factor*best);
  166.     else    /* Leave the opponent as few choices as possible */
  167.         return(analysis + factor*(best + nMoves/2));
  168. }
  169.  
  170.  
  171.  
  172. short analyze(move, color, flips, nFlips, board, trace)
  173. MoveRecord    move;
  174. MoveList    flips;
  175. int        *nFlips;
  176. BoardArray    board;
  177. int        trace;
  178. {
  179.     int        opponent;
  180.     register int    i, drow, dcol, nNeighbors;
  181.     short        value;
  182.     int        ticks;
  183.     
  184.     if (trace > 1)
  185.         PlaceStone(move.row, move.col, color);
  186.     board[move.row][move.col] =
  187.     board[move.row][move.col] & ~stoneColor | color;
  188.     board[move.row][move.col] |= flipped;
  189.     *nFlips = DoFlips(color, move, board, flips, INVISIBLE);
  190.     ticks = TickCount();
  191.     opponent = opposite(board[move.row][move.col]);
  192.     if ((value = position[move.row][move.col]) < -2)
  193.         value += value;        /* Placing as bad as flipping here */
  194.     nNeighbors = -1;
  195.     for (drow = -1; drow <= 1; ++drow)
  196.         for (dcol = -1; dcol <= 1; ++dcol)
  197.         if (board[move.row+drow][move.col+dcol] != stoneEmpty)
  198.             ++nNeighbors;
  199.     value += nNeighbors/2 - 3;    /* Keep stones bunched up */
  200.     if ((move.row == 1 || move.row == BOARDSIZE) &&
  201.         (board[move.row][move.col - 1] & stoneColor) == opponent &&
  202.         (board[move.row][move.col + 1] & stoneColor) == opponent)
  203.         value *= 4;
  204.     else if ((move.col == 1 || move.col == BOARDSIZE) &&
  205.         (board[move.row - 1][move.col] & stoneColor) == opponent &&
  206.         (board[move.row + 1][move.col] & stoneColor) == opponent)
  207.         value *= 4;
  208.     for (i = 0; i < *nFlips; ++i) {
  209.         nNeighbors = -1;
  210.         for (drow = -1; drow <= 1; ++drow)
  211.             for (dcol = -1; dcol <= 1; ++dcol)
  212.             if (board[flips[i].row+drow][flips[i].col+dcol] !=
  213.                 stoneEmpty)
  214.                 ++nNeighbors;
  215.         value += 2 * position[flips[i].row][flips[i].col] +
  216.             nNeighbors/2 - 3;    /* Keep stones bunched up */
  217.     }
  218.     if (trace > 2) {
  219.         sprintf(note1, "analyze = %d", value);
  220.         display(30);
  221.     }
  222.     nTicks[pAnalyze] += TickCount() - ticks;
  223.     return(value);
  224. }
  225.  
  226. RestoreBoard(board, move, flips, nFlips, trace)
  227. BoardArray    board;
  228. MoveRecord    move;
  229. MoveList    flips;
  230. int        nFlips;
  231. int        trace;
  232. {
  233.     register int    color;    /* color to change stones back to    */
  234.     register int    i;
  235.     int        ticks;
  236.     
  237.     ticks = TickCount();
  238.     color = opposite(board[move.row][move.col]);
  239.     if (trace > 1)
  240.         PlaceStone(move.row, move.col, stoneEmpty);
  241.     board[move.row][move.col] &= ~(flipped | stoneColor);
  242.     for (i = 0; i < nFlips; ++i) {
  243.         if (trace > 1)
  244.             PlaceStone(flips[i].row, flips[i].col, color);
  245.         board[flips[i].row][flips[i].col] =
  246.         board[flips[i].row][flips[i].col] & ~(flipped | stoneColor)
  247.                           | color;
  248.  
  249.     }
  250.     nTicks[pRestoreBoard] += TickCount() - ticks;
  251. }
  252.  
  253.  
  254.  
  255. SortMoves(moves, nMoves)
  256. MoveList    moves;
  257. int        nMoves;
  258. {
  259.     register int    i, nSorted;
  260.     int        max;
  261.     MoveRecord    temp;
  262.     int        ticks;
  263.     
  264.     ticks = TickCount();
  265.     for (nSorted = 0; nSorted < nMoves; ++nSorted) {
  266.         max = nSorted;
  267.         for (i = nSorted + 1; i < nMoves; ++i)
  268.             if (moves[i].value > moves[max].value)
  269.                 max = i;
  270.         if (max != nSorted) {
  271.             temp = moves[nSorted];
  272.             moves[nSorted] = moves[max];
  273.             moves[max] = temp;
  274.         }
  275.     }
  276.     nTicks[pSortMoves] += TickCount() - ticks;
  277. }
  278.